/**
 * 标准的01背包
 */
#include <bits/stdc++.h>
using namespace std;

int getInt(){
    char ch;
    while(not isdigit(ch = getchar()));
    
    int ret = ch ^ '0';
    while(isdigit(ch = getchar())) ret = ret * 10 + (ch ^ '0');
    return ret;
}

int T, M;
vector<int> W;
vector<int> Cost;
vector<int> D;
int main(){
    T = getInt();
    M = getInt();
    W.assign(M + 1, 0);
    Cost.assign(M + 1, 0);
    for(int i=1;i<=M;++i){
        Cost[i] = getInt();
        W[i] = getInt();
    }
    
    D.assign(T + 1, 0); 
    for(int i=1;i<=M;++i){
        for(int v=T;v>=Cost[i];--v){
            D[v] = max(D[v], D[v - Cost[i]] + W[i]);
        }
    }
    cout << D[T] << endl;
    return 0;
}